package com.edu.leetcode.dataStruct;

/**
 * 原地删除有序数组的重复元素(元素最多只能出现两次且不能使用额外空间)
 *
 * @作者 five-five
 * @创建时间 2021/4/6
 */
public class Demo11 {
    public static void main(String[] args) {
        Demo11 demo11 = new Demo11();
        int i = demo11.removeDuplicates(new int[]{1, 1, 1, 2, 2, 3});
        System.out.println(i);

    }

    /**
     * 给你一个有序数组 nums ，请你 原地 删除重复出现的元素，使每个元素 最多出现两次 ，返回删除后数组的新长度。
     * <p>
     * 不要使用额外的数组空间，你必须在 原地 修改输入数组 并在使用 O(1) 额外空间的条件下完成。
     * <p>
     * 来源：力扣（LeetCode）
     * 链接：https://leetcode-cn.com/problems/remove-duplicates-from-sorted-array-ii
     * 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
     *
     * @param nums
     * @return
     */
    public int removeDuplicates(int[] nums) {
        int n = nums.length;
        if (n <= 2) {
            return n;
        }
        int slow = 2, fast = 2;
        while (fast < n) {
            if (nums[slow - 2] != nums[fast]) {
                nums[slow] = nums[fast];
                ++slow;
            }
            ++fast;
        }
        return slow;
    }
}
